const INF = Number.MAX_SAFE_INTEGER; // int范围内的最大值
/**
 * 迪杰斯特拉(Dijkstra)算法核心是贪心算法，求出图里各个顶点到源顶点的最短距离和具体路径
 * @param graph 图的邻接矩阵形式（顶点和顶点之间的关系，值是权值）
 * @param src 源顶点
 */
export const dijkstra = (graph: number[][], src: number) => {
    const dist: number[] = []; // 保存每个顶点距离源顶点的最小值
    const visited: boolean[] = []; // 保存每个顶点的处理状态
    const predecessors: number[] = []; // 回溯顶点的下标（可组成路径）
    const length: number = graph.length; // 图中顶点的个数

    // 初始化dist和visited
    for (let i = 0; i < length; i ++) {
        dist[i] = INF;
        visited[i] = false;
        predecessors[i] = -1;
    }
    dist[src] = 0; // 源顶点自身距离是0
    for (let i = 0; i < length - 1; i ++) { // length减一是因为不包含源顶点本身
        const u = minDistance(dist, visited); // 只计算列表中距离源顶点最近的顶点(要是可访问)，贪心点1
        // 查看它的可访问邻接顶点
        for (let v = 0; v < length; v ++) { // 这里没有减一是因为下面会避开u自身
            if (!visited[v] && graph[u][v] !== 0 // 避开不可访问的，也避开了u自身，也避开非邻接顶点
                && graph[u][v] + dist[u] < dist[v]) { // 如果u到源顶点最短路径加上这条边的权值，小于邻接顶点现存的最短路径

                dist[v] = graph[u][v] + dist[u]; // 更新邻接顶点现存的最短路径，贪心点2
                predecessors[v] = u; // 更新回溯点
            }
        }
        visited[u] = true; // u处理了
    }
    return { dist, predecessors };
};
/**
 * 找出列表中距离源顶点最近的顶点(要是可访问)
 * @param dist 每个顶点距离源顶点的最小值
 * @param visited 每个顶点的访问状态
 */
const minDistance = (dist: number[], visited: boolean[]) => {
    let minIndex = -1;
    let min = INF;
    for (let i = 0; i < dist.length; i ++) {
        if (!visited[i] && dist[i] < min) { // 可访问并且有更小的
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
};
